#include "combine.h"

vector<double> _ccp;
bool comp(const pair<bset,int>& p1, const pair<bset,int>& p2) {
	double r=0.0;
	forn(i,_ccp.size()) if (p1.first[i] != p2.first[i]) 
		r+=p1.first[i]?_ccp[i]:-_ccp[i];
	return r>0.0;
}

void fix(vector<pair<bset,int> >& v, int csets, int m, double alpha) {
	//eliminar sets incluidos en otros
	forn(i,v.size()) {
		forn(j,v.size())if (i!=j) {
			if ((v[j].first | v[i].first) == v[j].first) { //si v[i] incluido en v[j]
				swap(v[i],v[v.size()-1]);
				v.pop_back();
				i--;
				break;
			}
		}
	}
	if (csets>=v.size()) return;
	//rankear y quedarse con los csets mejores
	_ccp=vector<double>(m);
	forn(i,v.size())forn(j,m) if (v[i].first[j]) _ccp[j]++;
	forn(j,m) _ccp[j]=alpha+1.0/_ccp[j];
	sort(v.begin(), v.end(), comp);
	v.resize(csets);
}

vector<pair<bset,vector<bomba> > > getBests(const vector<pair<bset,vector<bomba> > >& initial, int k,
	double alpha, int csets, int m) {
	vector<pair<bset,vector<bomba> > > r;
	const vector<pair<bset,vector<bomba> > >* sp;
	if (k==1) {
		return initial;
	} else if (k&1) { //k is odd
		r=getBests(initial,k-1,alpha,csets,m);
		sp=&initial;
	} else {
		r=getBests(initial,k/2,alpha*0.9,csets,m);
		sp=&r;
	}
	const vector<pair<bset,vector<bomba> > >& s=*sp;
	vector<pair<bset,int> > t(r.size()*s.size());
	forn(i,r.size())forn(j,s.size()) {
		int k=i*s.size()+j;
		t[k].first=r[i].first | s[j].first;
		t[k].second=k;
	}
	fix(t,csets,m,alpha);
	vector<pair<bset,vector<bomba> > > res(t.size());
	forn(i,t.size()) {
		res[i].first=t[i].first;
		int ir=t[i].second/s.size();
		int is=t[i].second%s.size();
		res[i].second.resize(r[ir].second.size()+s[is].second.size());
		forn(j,r[ir].second.size()) res[i].second[j]=r[ir].second[j];
		forn(j,s[is].second.size()) res[i].second[j+r[ir].second.size()]=s[is].second[j];
	}
	return res;
}

vector<bomba> getBest(const vector<pair<bset,bomba> >& initial, int k, int csets, int m) {
	vector<pair<bset,vector<bomba> > > initialV(initial.size());
	forn(i,initial.size()) {
		initialV[i].first=initial[i].first;
		initialV[i].second=vector<bomba>(1, initial[i].second);
	}
	vector<pair<bset,vector<bomba> > > r = getBests(initialV, k, 1, csets, m);
	int mi=0,ms=0;
	forn(i,r.size())if (r[i].first.count()>ms) {
		ms=r[i].first.count();
		mi=i;
	}
	return r[mi].second;
}
